using System;
using System.Collections.Generic;

namespace GraphSpace
{
	public class BinaryHeap : IPQ
	{
		public List<Knoten> Heap;
		private int deleteMinCounter;

        public void init (int C)
        {
        	deleteMinCounter = 0;
		}

		public double getMinDistance ()
		{
				return Heap[0].distance;
		}
		
		public BinaryHeap ()
		{
			deleteMinCounter = 0;
			Heap = new List<Knoten> ();
		}

		public bool insert (Knoten item)
		{
			Heap.Add (item);
			item.position = Heap.Count;
			int aktPos = Heap.Count;
			//TODO heapyfy aufrufen auf item
			if (Heap.Count > 1)
				while (aktPos != 1 && Heap[aktPos - 1].distance < Heap[aktPos / 2 - 1].distance) 
				{
					Knoten tmp = Heap[aktPos / 2 - 1];
					Heap[aktPos / 2 - 1] = Heap[aktPos - 1];
					Heap[aktPos / 2 - 1].position = (aktPos / 2);
					Heap[aktPos - 1] = tmp;
					Heap[aktPos - 1].position = aktPos;
					aktPos = aktPos / 2;
				}
			
			return true;
		}

		public bool delete (int item)
		{
			if (Heap.Count > 2)
			{
				Knoten tmp = Heap[item - 1];
				Heap[item - 1] = Heap[Heap.Count - 1];
				Heap[item - 1].position = item;
				Heap[Heap.Count - 1] = tmp;
				Heap[Heap.Count - 1].position = Heap.Count;
				Heap.RemoveAt (Heap.Count - 1);
				
				// TODO Heapyfy auf item
				heapify (1);
				
				return true;
			}
			
			if (Heap.Count == 1)
			{
				Heap.RemoveAt (0);
				return true;
			}
			
			if (Heap.Count == 0)
				return false;
			
			return false;
		}

		public Knoten extractHead ()
		{
			if (Heap.Count == 0)
				return null;
			
			Knoten Min;
			if (Heap.Count > 1)
			{
				Min = Heap[0];
				Knoten tmp = Heap[Heap.Count - 1];
				Heap[Heap.Count - 1] = Heap[0];
				Heap[Heap.Count - 1].position = Heap.Count;
				Heap[0] = tmp;
				Heap[0].position = 1;
				Heap.RemoveAt (Heap.Count - 1);
				deleteMinCounter++;
				
				
				// TODO Heapyfy auf Wurzel
				heapify (1);
			}
			else
			{
				Min = Heap[0];
				Heap.RemoveAt (0);
			}
			return Min;
			
		}

		public int getDeleteMinCounter ()
		{
			return deleteMinCounter;
		}
		
		public bool decreaseKey (Knoten item, double Key)
		{
			Heap[item.position - 1].distance = Key;
			
			int aktPos = item.position;
			if (Heap.Count > 0)
			{
				while (aktPos != 1 && Heap[aktPos - 1].distance < Heap[aktPos / 2 - 1].distance ) 
				{
					Knoten tmp = Heap[aktPos / 2 - 1];
					Heap[aktPos / 2 - 1] = Heap[aktPos - 1];
					Heap[aktPos / 2 - 1].position = (aktPos / 2);
					Heap[aktPos - 1] = tmp;
					Heap[aktPos - 1].position = aktPos;
					aktPos = aktPos / 2;
				}
			}
			
			return true;
		}

		// Vater = abgerundet(2/n)
		// linker Bruder = 2n
		// rechter Bruder = 2n + 1
		private void heapify (int item)
		{
			
			int left = item * 2;
			int right = item * 2 + 1;
			int largest = item;
			
			if (left < Heap.Count && Heap[left - 1].distance < Heap[item - 1].distance)
				largest = left;
			
			if (right < Heap.Count && Heap[right - 1].distance < Heap[largest - 1].distance)
				largest = right;
			
			if (largest != item) {
				Knoten tmp = Heap[item - 1];
				Heap[item - 1] = Heap[largest - 1];
				Heap[item - 1].position = item;
				Heap[largest - 1] = tmp;
				Heap[largest - 1].position = largest;
				heapify (largest);
			}
		}

		public bool isEmpty ()
		{
			return Heap.Count == 0;
		}
	}
}

